package leetcode.code572;

import leetcode.helper.tree.TreeNode;

public class Solution1 extends Solution572 {

	@Override
	public boolean isSubtree(TreeNode root, TreeNode subRoot) {
		if (root == null && subRoot == null)
			return true;
		if ((root == null && subRoot != null) || (root != null && subRoot == null))
			return false;
		if (isSubtree(root.left, subRoot))
			return true;
		if (isSubtree(root.right, subRoot))
			return true;
		if (root.val == subRoot.val) {
			boolean left = this.isSubtreeHead(root.left, subRoot.left);
			boolean right = this.isSubtreeHead(root.right, subRoot.right);
			if (left && right && root.val == subRoot.val)
				return true;
		}
		return false;
	}

	public boolean isSubtreeHead(TreeNode root, TreeNode subRoot) {
		if (root == null && subRoot == null)
			return true;
		if (root != null && subRoot != null && root.val == subRoot.val) {
			boolean left = this.isSubtreeHead(root.left, subRoot.left);
			boolean right = this.isSubtreeHead(root.right, subRoot.right);
			if (left && right && root.val == subRoot.val)
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		Solution1 so = new Solution1();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();
	}

}
